package leetcode75;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TextEx {
    //交替合并字符
    public static String mergeAlternately(String word1, String word2) {
//        String words = "";
//        char[] array1 = word1.toCharArray();
//        char[] array2 = word2.toCharArray();
//        int word1Length = array1.length;
//        int word2Length = array2.length;
//        int maxLength = Math.max(word1Length, word2Length);
//        for (int i = 0; i < maxLength; i++) {
//            if (i < word1Length) words += array1[i];
//            if (i < word2Length) words += array2[i];
//        }
//        return words;

        int m = word1.length(), n = word2.length();
        int i = 0, j = 0;

        StringBuilder ans = new StringBuilder();
        while (i < m || j < n) {
            if (i < m) {
                ans.append(word1.charAt(i));
                ++i;
            }
            if (j < n) {
                ans.append(word2.charAt(j));
                ++j;
            }
        }
        return ans.toString();
    }

    //字符串的最大公因子
    public static String gcdOfStrings(String str1, String str2) {
//        int s1Len = str1.length();
//        int s2Len = str2.length();
//        int minLen = Math.min(s1Len, s2Len);
//        int maxLen = Math.max(s1Len, s2Len);
//        String minStr = s1Len > s2Len ? str2 : str1;
//        String maxStr = s1Len > s2Len ? str1 : str2;
//        String ans = "";
//        //重复逻辑需要进行抽离
//        for (int i = minLen; i > 0; i--) {
//            String temp = minStr.substring(0, i);
//            int minCir = minLen / i;
//            int maxCir = maxLen / i;
//            StringBuilder minRes = new StringBuilder();
//            StringBuilder maxRes = new StringBuilder();
//            if (minLen % i == 0 && maxLen % i == 0) {
//                for (int j = 0; j < minCir; j++) {
//                    minRes.append(temp);
//                }
//                for (int k = 0; k < maxCir; k++) {
//                    maxRes.append(temp);
//                }
//                if (minStr.equals(minRes.toString()) && maxStr.equals(maxRes.toString())) {
//                    ans = temp;
//                    break;
//                }
//            }
//        }
//        return ans;

        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; --i) { // 从长度大的开始枚举
            if (len1 % i == 0 && len2 % i == 0) {
                String X = str1.substring(0, i);
                if (check(X, str1) && check(X, str2)) {
                    return X;
                }
            }
        }
        return "";
    }

    //拥有最多糖果的孩子
    public static List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maxCandy = 0;
        List<Boolean> resList = new ArrayList<>();
        for (int i = 0; i < candies.length; i++) {
            int candy = candies[i];
            if (candy > maxCandy) {
                maxCandy = candy;
            }
        }
        for (int i = 0; i < candies.length; i++) {
            int candy = candies[i];
            resList.add(maxCandy - candy <= extraCandies);
        }

//        Iterator it = candyList.iterator();
//        System.out.println("candyList:"+ candyList.toString());
//        while(it.hasNext()) {
//            int num = (Integer) it.next();
//            if (num > maxCandy) {
//                maxCandy = num;
//            }
//        }
//        while(it.hasNext()) {
//            int num = (Integer) it.next();
//            resList.add(maxCandy - num >= 0);
//        }
        return resList;
    }

    //种花问题
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
//        List<Integer> list = new ArrayList<>();
//        int addFlowerNum = 0;
//        for (int i = 0; i < flowerbed.length; i++) {
//            list.add(flowerbed[i]);
//        }
//        int size = list.size();
//        if (size == 1 && list.get(0) == 0) {
//            return true;
//        }
//        if (list.size() >= 2 && (list.get(0) == 0 && list.get(1) == 0)) {
//            list.set(0,1);
//            addFlowerNum++;
//        }
//        if (list.size() >= 2 && (list.get(size-2) == 0 && list.get(size-1) == 0)) {
//            list.set(size-1,1);
//            addFlowerNum++;
//        }
//
//        for (int i = 1; i < list.size() - 1; i++) {
//            int fFlower = list.get(i-1);
//            int aFlower = list.get(i+1);
//            int cFlower = list.get(i);
//            if (fFlower == 0 && aFlower == 0 &&  cFlower == 0) {
//                addFlowerNum++;
//                list.set(i, 1);
//            }
//        }
//
//        return addFlowerNum >= n;

        for (int i = 0, len = flowerbed.length; i < len && n > 0;) {
            if (flowerbed[i] == 1) {
                i += 2;
            } else if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
                n--;
                i += 2;
            } else {
                i += 3;
            }
        }
        return n <= 0;
    }

    public static boolean check(String t, String s) {
        int lenx = s.length() / t.length();
        StringBuilder ans = new StringBuilder();
        for (int i = 1; i <= lenx; ++i) {
            ans.append(t);
        }
        return ans.toString().equals(s);
    }


    //移动零
    public static void moveZeroes(int[] nums) {
        System.out.println("before moveZeroes:"+ Arrays.toString(nums));
//        if (nums.length > 1) {
//            for (int i = 0; i < nums.length; i++) {
//                int currentNum = nums[i];
//                for (int j = i + 1; j < nums.length; j++) {
//                    if (currentNum == 0 && nums[j] != 0) {
//                        nums[i] = nums[j];
//                        nums[j] = 0;
//                        break;
//                    }
//                }
//            }
//        }

//        //复杂度O(n)
//        if(nums==null) {
//            return;
//        }
//        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
//        int j = 0;
//        for(int i=0;i<nums.length;++i) {
//            if(nums[i]!=0) {
//                nums[j++] = nums[i];
//            }
//        }
//        //非0元素统计完了，剩下的都是0了
//        //所以第二次遍历把末尾的元素都赋为0即可
//        for(int i=j;i<nums.length;++i) {
//            nums[i] = 0;
//        }


        //一次遍历
        if(nums==null) {
            return;
        }
        //两个指针i和j
        int j = 0;
        for(int i=0;i<nums.length;i++) {
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if(nums[i]!=0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }

        System.out.println("after moveZeroes:"+ Arrays.toString(nums));
    }

    public static boolean canPlaceFlowers(String s, String t) {
//        if (s.length() > t.length()) {
//            return false;
//        }
//        int index = 0;
//        int nums = 0;
//        for (int j = 0; j < s.length(); j++) {
//            char sChar = s.charAt(j);
//            for (int k = index; k < t.length(); k++) {
//                if (sChar == t.charAt(k)) {
//                    nums++;
//                    index = k + 1;
//                    break;
//                }
//            }
//        }
//        return nums == s.length();

        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }

    //连续子数组平均数
    public static double findMaxAverage(int[] nums, int k) {
        //审题错误，需要连续子数组！！！
//        float sum = 0;
//        //先从大到小排序
//        for (int i = 0; i < k; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                if (nums[j] > nums[i]) {
//                    int temp = nums[i];
//                    nums[i] = nums[j];
//                    nums[j] = temp;
//                }
//            }
//            sum += nums[i];
//        }
//        return sum / k;
        //不能每次遍历都重新计算，会导致时间复杂度过高
        double sum = 0;
        double maxSum = -Double.MAX_VALUE;
        for (int i = 0; i <= nums.length - k; i++) {
            if (i == 0) {
                int index = 0;
                while (index < k) {
                    sum += nums[i+index];
                    index++;
                }
            } else {
                sum = sum - nums[i-1] + nums[i+k-1];
            }
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
        return maxSum / k;
    }

    //字符串解码
    public static String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        int index = 0;
        int num = 0;
        int numIndex = 0;
        int rightIndex = 0;
        char rightStr = ']';
        while(index < s.length()) {
            if (s.toCharArray()[index] > 0) {
                num = s.charAt(index);
                numIndex = index;
            }
            if (rightStr==s.toCharArray()[index]) {
                rightIndex = index;
            }
            if (num > 0 && numIndex > 0 && rightIndex > 0) {
                while (num > 0) {
                    result.append(s, numIndex + 2, rightIndex);
                    num--;
                }
                numIndex = 0;
                rightIndex = 0;
            }
            index++;
        }
        return result.toString();
    }

    public static int[] array = new int[] {10, 5, 2, 6};
    public static int numSubArrayProductLessThanK(int[] nums, int k) {
        int left = 0;
        int count = 0;
        int sub = 1;
        for (int right = 0; right < nums.length; right++) {
            sub *= nums[right];
            while (left <= right && sub >= k) {
                sub /= nums[left++];
            }
            count += left <= right ? right - left + 1 : 0;
        }
        return count;
    }

    public static void main(String[] args) {
//        System.out.println("getValue:" + gcdOfStrings("ABCABC", "ABC"));
//        System.out.println("kidsWithCandies:"+ kidsWithCandies(new int[] {2,3,5,1,3}, 3));
//        System.out.println("canPlaceFlowers:"+ canPlaceFlowers(new int[] {1,0,3,0,1}, 1));
//        moveZeroes(new int[] {1,0,33,0,1});
//        System.out.println("canPlaceFlowers:"+ canPlaceFlowers("axc", "ahbgdc"));
//        System.out.println("findMaxAverage:"+ findMaxAverage(new int[] {-1}, 1));
//        System.out.println("decodeString:"+ decodeString("3[a]2[bc]"));
        System.out.println("numSubArrayProductLessThanK:"+ numSubArrayProductLessThanK(array, 100));
    }
}
